\documentclass[11pt,a4wide,twoside]{article}
\author{Ivan Bogouchev}
\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}
\title{Huffman Adaptatif}
\frenchspacing
\begin{document}
\maketitle
\section{Introduction}
Le codage de Huffman est le r\'esultat des traveaux de prof David A. Huffman.
C'est une m\'ethode de compression sans perte d'information qui repose
sur le fait que chaque symbole a une fr\'equence d'apparition
diff\'erente. Donc on associe \`a chaque symbole un code diff\'erent,
tel que plus la fr\'equence d'apparition d'un symbole est grande, moins
son code est long.

Comme c'est un codage \'a longueur variable, les codes produits
doivent former un code pr\'efixe. Ce code peut \^etre repr\'esent\'e
par un arbre binaire, o\`u chaque symbole \`a coder se trouve dans les
feuilles et le code correspondant est obtenu en rempla\c cant dans le
parcours de la feuille \`a la racine les ar\^etes gauches par un 0 et
les ar\^etes droites par un 1.

En g\'en\'erale il y a deux m\'ethodes pour obtenir les codes et
l'arbre correspondant:
\begin{description}
\item[Statique:] l'arbre est construit \`a partir d'une table contenant
  les fr\'equences des caract\`eres
\item[Dynamique:] l'arbre \'evolue au fur et \`a mesure
\end{description}

\section{Expos\'e du probl\`eme}
Il y a plusieurs probl\`emes avec la m\'ethode statique:
\begin{itemize}
\item Besoin soit d'avoir une table de fr\'equences universelle, soit
  de parcourrir le texte deux fois (pour avoir les fr\'equences et
  pour le compresser)
\item Plusieurs arbres possibles pour une m\^eme table de fr\'equences
\item Les fr\'equences sont pris en compte pour la totalit\'e du texte
\end{itemize}

L'algorithme de Huffman dynamique r\'esout ces probl\`emes:
\begin{itemize}
\item Pas besoin de parcourir le texte deux fois
\item Le compresseur et le d\'ecompresseur ont exactement les m\^emes
  arbres \`a un instant donn\'e.
\item Si un symbole apparait souvent au d\'ebut du text, mais apparait
  tr\'es peu \`a la fin, son code sera cour au d\'ebut et deviendra de
  plus en plus long par la suite
\end{itemize}

\section{Rappel de l'algorithme}
\subsection{Proc\'edures auxili\`eres}
\subsubsection{Modification}

\begin{verbatim}
Fonction Modification (H, s)
Si s n'est pas dans H
   Soit Q le pere de la feuille speciale #
   Remplacer # par un noeud interne de poids 1, dont
      - le fils gauche est #
      - le fils droit est une feuille de poids 1, contenant s
Sinon
   Soit Q la feuille, correspondat a s
FinSi
retourne Traitement(Q)   
\end{verbatim}

\subsubsection{Traitement}

\begin{verbatim}
Fonction Traitement (H, Q)
Tantque Q n'est pas vide Faire -- pere (racine) -> vide
   EoB = FinBlock (Q)
   Si Q == EoB Alors
      IncrementerPoids (Q)
      Q = Pere (Q)
   Sinon
      Echanger (Q, EoB)
      Q = EoB
   FinSi
FinTantque
\end{verbatim}

\subsection{Compression}

\begin{verbatim}
ENTREE : Texte T
SORTIE : Texte TC
c = LireCaractere (T)
H = Arbre (c) -- un arbre ou le fg de la racine est #
              -- et fd est le caractere c
Tantque non estVide (T) Faire
   c = LireCaractere (T)
   Si c est dans H alors
      Transmettre le code actuel de c
   Sinon
      Transmettre le code actuel de #
      Transmettre le code initial de c
   FinSi
   Modification (H, c)
FinTantque
\end{verbatim}

\subsection{Decompression}

\begin{verbatim}
ENTREE : Texte TC
SORTIE : Texte T
c = LireCaractere (T)
H = Arbre (c)
Noeud n = Racine (H)

Tantque non estVide (TC)
   b = LireBit (TC)
   Si b == 0 Alors
      n = FilsGauche (n)
   Sinon
      n = FilsDroit (n)
   FinSi

   Si estFeuille (n) alors
      Si estSpeciale (n) alors
         c = LireKbits (TC)
      Sinon
         c = Caractere (n)
      FinSi
      Modification (H, c)
FinTantque
\end{verbatim}

\section{Structures de don\'ees}
\subsection{Arbre de Huffman}
\subsubsection{Les noeuds}
\begin{verbatim}
typedef struct huff_node_struct {
  int w;           // le poids
  int c;           // le caractere
  int gdbh_index;  // index dans gdbh
  struct huff_node_struct *father;  
  struct huff_node_struct *left;
  struct huff_node_struct *right;
} *huff_node;
\end{verbatim}
Chaque noeud \emph n contient le caract\'ere dans \emph{n->c} ou -1 si c'est
un noeud interne. Le \emph{gdbh\_index} nous permet de retrouver la position
du noeud dans l'ordre \emph GDBH de l'arbre.

\subsubsection{L'arbre}
\begin{verbatim}
typedef struct huff_tree_struct {
  huff_node root;       // la racine
  huff_node special;    // le pere de diese
  huff_node chars[256]; // hash char -> huff_node
  huff_node gdbh[512];  // l'ordre gdbh
  int count;            // nobre de symboles
} huff_tree;

extern huff_tree thetree;
\end{verbatim}
Dans l'implantaion j'ai choisi pr\'esenter la feuille sp\'eciale par
NULL. On a donc dans thetree->special le p\`ere de \#.

\emph{thetree->chars} est un tableau (de hachage) qui nous permet de trouver
la feuille correspondant \`a un caract\`ere et de tester si le
caract\`ere a d\'ej\`a \'ete rencontr\'e (si c'est pas le cas, il y a NULL \`a
cet empla\c cement dans le tableau. La taille du tableau est 256 car
on a choisit une longueur de huit bits pour les symboles.

\emph{thetree->gdbh} est un tableau qui, \'a chaque instant contient
tous les noeuds de l'arbre tri\'es dans l'ordre GDBH. Comme il'y a au
plus 256 symboles \`a coder (qui sont sur les feuilles) et c'est un
arbre binaire complet, alors on a ou plus 256 noeuds internes (le \#
n'occupe pas neoud). Donc la taille de \emph{thetree->gdbh} est 512

Et on exporte un arbre qui sera utilis\'e par le compresseur et le decompresseur.

\subsubsection{Code de Huffman}
\begin{verbatim}
typedef struct huff_code_struct {
  int length;  // la longueur de ce code
  int bits;    // et le code
} *huff_code;
\end{verbatim}

\subsection{Bit IO}
\subsubsection{Flot de bits}
\begin{verbatim}
typedef struct _bitiob {
  int count;  // nombre de bits restant
  char *ptr;  // octet courrant
  char *base; // debut du tampon
  int fd;     // descripteur de fichier soujacent
} *bf_stream;
\end{verbatim}
Structure qui nous permet de bufferiser les entr\'ees/sorties de bit.
Le bf\_* est pour bitfield.


\section{Presentation du fonctionnement et Inventaire des fichiers}
J'ai divis\'e le devoir en trois parties:

\begin{tabular}{|c||c|}
\hline
compress.c & decompress.c \\
\hline
\multicolumn{2}{|c|}{huff\_putcode()}\\
\cline{1-1}
\multicolumn{1}{|c|}{bf.c} & huffman.c \\
\hline
\end{tabular}

\begin{enumerate}

\item huffman.c contient les operations sur l'arbre et sur les noeuds.
\begin{itemize}
\item[-] huff\_tree\_new () // nouveau noeud
\item[-] huff\_tree\_update () // traitement dans le cours
\item[-] huff\_tree\_modify () // modification dans le cours\\

\item[-] huff\_node\_new () // nouveau noued
\item[-] huff\_node\_exchange () // echoanger deux noeuds
\item[-] huff\_node\_isgdbh () // vrai si le succ(n) est de poid > n
\item[-] huff\_node\_eob () // fin de block
\item[-] huff\_node\_get\_code () // parcourir l'arbre pour avoir le code
\item[-] huff\_node\_isspecial () est'ce le pere de diese\\
\item[-] huff\_getcode () // trouver le code associe a un caractere
\end{itemize}

\item Bit IO
\begin{itemize}
\item[-] bf\_open () // renvoi un nouveau tampon attache au fichier
\item[-] bf\_close () // ferme 
\item[-] bf\_putbit () // emmetre un bit
\item[-] bf\_getbit () // en recevoir un
\item[-] bf\_putchar () // emmetre huit bits
\item[-] bf\_getchar () // recevoir huit bits
\item[-] bf\_align () // completer avec des 0 aligner avec les octets


\end{itemize}

\item Le compresseur: usage : compresseur <inputfile> <outputfile>
si <inputfile> et - , alors le compresseur lit depuis stdin
si <outputfile et - , alros le compresseur ecrit dans stdout

\item Le decompresseur : idem

Cela permet de faire:\\
\mbox{./compresseur foo - | ./decompresseur - bar}\\
\mbox{diff foo bar \&\& echo Super}

\end{enumerate}

\section{Taux de compression}
\begin{tabular}{|r|r|r|r|r|r|r|r|}
\hline
fichier: & test0 & test1 & test2 & test2rev & test3 & test4 & test10\\
\hline
taille originelle & 3000 & 2046 & 65534 & 65534 & 80000 & 1048574 & 97005568\\
\hline
taille compress\'e & 1893 & 525 & 16406 & 16395 & 54290 & 262180 & 13098826\\
\hline
\end{tabular}

\tableofcontents
\end{document}
